public class Solution1463 {
    public int cherryPickup(int[][] grid) {
        int[][] f=new int[grid[0].length][grid[0].length];
        for (int i=0;i<grid[0].length;i++){
            for (int j=0;j<grid[0].length;j++){
                f[i][j]=Integer.MIN_VALUE;
            }
        }
        f[0][grid[0].length-1]=grid[0][0]+grid[0][grid[0].length-1];
        for (int k=1;k<grid.length;k++){
            int[][] g=new int[grid[0].length][grid[0].length];
            for (int i=0;i<grid[0].length;i++){
                for (int j=0;j<grid[0].length;j++){
                    g[i][j]=Integer.MIN_VALUE;
                    int add=grid[k][i]+grid[k][j];
                    if (i==j){
                        add/=2;
                    }
                    g[i][j]=Math.max(g[i][j],f[i][j]+add);
                    if (j>0){
                        g[i][j]=Math.max(g[i][j],f[i][j-1]+add);
                    }
                    if (j<grid[0].length-1){
                        g[i][j]=Math.max(g[i][j],f[i][j+1]+add);
                    }
                    if (i>0){
                        g[i][j]=Math.max(g[i][j],f[i-1][j]+add);
                        if (j>0){
                            g[i][j]=Math.max(g[i][j],f[i-1][j-1]+add);
                        }
                        if (j<grid[0].length-1){
                            g[i][j]=Math.max(g[i][j],f[i-1][j+1]+add);
                        }
                    }
                    if (i<grid[0].length-1){
                        g[i][j]=Math.max(g[i][j],f[i+1][j]+add);
                        if (j>0){
                            g[i][j]=Math.max(g[i][j],f[i+1][j-1]+add);
                        }
                        if (j<grid[0].length-1){
                            g[i][j]=Math.max(g[i][j],f[i+1][j+1]+add);
                        }
                    }
                }
            }
            f=g;
        }
        int ans=0;
        for (int i=0;i<grid[0].length;i++){
            for (int j=0;j<grid[0].length;j++){
                ans=Math.max(ans,f[i][j]);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1463().cherryPickup(new int[][]{{3,1,1},{2,5,1},{1,5,5},{2,1,1}}));
    }
}
